package william.recursive;

import java.util.HashMap;
import java.util.Map;

/**
 * @author ZhangShenao
 * @date 2024/1/8
 * @description <a href="https://leetcode.cn/problems/climbing-stairs/">...</a>
 */
public class Leetcode70_爬楼梯 {
    /**
     * 使用Map保存中间结果,减少重复计算
     */
    private Map<Integer, Integer> cache = new HashMap<>();

    /**
     * 递归算法: 自顶向下
     * n阶楼梯的爬法=(第一次爬1阶,其余n-1阶的爬法) + (第一次爬2阶,其余n-2阶的爬法)
     * 递推公式: f(n)=f(n-1)+f(n-2)
     * 采用HashMap保存中间结果,减少重复计算
     * 时间复杂度O(N)
     * 空间复杂度O(N) 额外申请一个HashMap,长度为n
     */
    public int climbStairs(int n) {
        //递归终止条件
        if (n == 0 || n == 1) {
            return 1;
        }

        //首先从缓存中查找结果
        if (cache.containsKey(n)) {
            return cache.get(n);
        }

        //缓存miss,进行递归计算,并将结果保存在缓存中
        int result = climbStairs(n - 1) + climbStairs(n - 2);
        cache.put(n, result);

        //返回结果
        return result;
    }

}
